package com.leetcode.no32;

import java.util.*;

public class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        if (len <= 1) {
            return 0;
        }

        int res = 0;
        Stack<Integer> stack = new Stack<>();
        stack.add(-1);

        for (int i = 0; i < len; i++) {
            switch (s.charAt(i)) {
                case '(':
                    stack.push(i);
                    break;
                case ')':
                    stack.pop();
                    if (stack.isEmpty()) {
                        stack.push(i);
                    } else {
                        res = Math.max(i - stack.peek(), res);
                    }
                    break;
                default:
                    break;
            }
        }

        return res;
    }

    public int longestValidParentheses01(String s) {
        int len = s.length();
        if (len < 2) {
            return 0;
        }

        // dp[i]表示以i为结尾的最长有效括号长度
        // dp[0] = 0
        int[] dp = new int[len];
        int res = dp[0];

        for (int i = 1; i < len; i++) {

            if (s.charAt(i) == '(') {
                dp[i] = 0;
            } else {
                // i所在的位置是')'
                // 向前匹配左括号

                // 处理独立括号对的情形  类似()()、()(())
                if (s.charAt(i - 1) == '(') {
                    dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
                } else {
                    // 在
                    int pre = i - 1 - dp[i - 1];

                    // 如果是左括号，则更新匹配长度
                    if (pre >= 0 && s.charAt(pre) == '(') {
                        dp[i] = pre - 1 >= 0 ? dp[i - 1] + 2 + dp[i - dp[i - 1] - 2] : dp[i - 1] + 2;
                    }
                }
            }
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}
